package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/binary-tree-postorder-traversal/">二叉树的后序遍历 [简单]</a>
 * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历
 * 提示：
 * 树中节点的数目在范围 [0, 100] 内
 * -100 <= Node.val <= 100
 * 进阶：不使用递归，使用循环
 *
 * @author zhenzicheng
 * @date 2022-06-04 16:53
 */
public class BinaryTreePostorderTraversal_145 {

  /**
   * 递归遍历
   */
  // public List<Integer> postorderTraversal(TreeNode root) {
  //   List<Integer> res = new ArrayList<>();
  //   accessTree(root, res);
  //
  //   return res;
  // }
  //
  // public void accessTree(TreeNode root, List<Integer> res) {
  //   if (root == null) {
  //     return;
  //   }
  //
  //   accessTree(root.left, res);
  //   accessTree(root.right, res);
  //   res.add(root.val);
  // }

  /**
   * 循环遍历
   */
  public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>(); // 使用栈结构
    TreeNode cur = root, pre = null; // 定义当前节点和上一次访问的节点

    while (cur != null || !stack.isEmpty()) { // 只有当前节点和栈都为null才代表遍历结束
      while (cur != null) {
        stack.push(cur);
        cur = cur.left;
      }
      cur = stack.pop(); // 弹出一个元素
      // 当前节点右孩子为空或者右孩子已经遍历过了才输出
      if (cur.right == null || cur.right == pre) {
        res.add(cur.val);
        pre = cur;
        cur = null; // 置空代表下次遍历还会一直遍历cur的所有左孩子
      } else { // 如果不满足条件代表需要遍历右孩子
        stack.push(cur); // 将当前节点重新入栈，否则再弹出后就会导致上一次parent丢失
        cur = cur.right; // 遍历右边
      }
    }

    return res;
  }


}
